/*
 * Author: Wang Hsutung
 * Date: 2015/11/05
 * Locale: Wuhan, Hubei
 * Email: hsu[AT]whu.edu.cn
 */

#include <iostream>
#include <string>
#include <sstream>
#include <cctype>
#include <cassert>

using namespace std;

struct nodeRelation {
    char current;
    char parent;
    bool left;
    bool empty()
    {
        return current == '\0';
    }
    void clear()
    {
        current = '\0';
    }
    friend istream &operator >>(istream &in, nodeRelation &nr);
};

istream &operator >>(istream &in, nodeRelation &nr)
{
    string str;
    if (in >> str) {
        assert(str.size() > 3);
        nr.current = str[0];
        nr.parent = str[2];
        nr.left = (str.size() == 4 || toupper(str[3]) != 'R');
    } else {
        nr.clear();
    }
    return in;
}

struct node {
    char ch;
    node *left;
    node *right;

    node(char c, node *l = NULL, node *r = NULL) :
        ch(c), left(l), right(l) {}

    static void print(node *p, string prefix = "")
    {
        if (!p) {
            cout << "(null)" << endl;
            return;
        }
        cout << p->ch << endl;

        if (p->left || p->right) {
            cout << prefix << "├── ";
            print(p->left,  prefix + "│   ");
            cout << prefix << "└── ";
            print(p->right, prefix + "    ");
        }
    }

    static void build(node *p, istream &in)
    {
        static nodeRelation ahead;
        if (ahead.empty() && in) {
            in >> ahead;
        }
        if (ahead.parent != p->ch)
            return;

        if (ahead.left) {
            p->left = new node(ahead.current);
            if (in >> ahead && ahead.parent == p->ch) {
                p->right = new node(ahead.current);
                ahead.clear();
            }
            build(p->left, in);
            if (p->right)
                build(p->right, in);
        } else {
            p->right = new node(ahead.current);
            ahead.clear();
            build(p->right, in);
        }
    }
};

struct binTree {
    node *root;

    void construct(istream &in)
    {
        char tmp;
        if (in >> tmp) {
            root = new node(tmp);
            node::build(root, in);
        } else {
            root = NULL;
        }
    }

    void construct(string str)
    {
        stringstream ss(str);
        construct(ss);
    }
    void print(void)
    {
        node::print(root);
    }
};

int main(int argc, char *argv[])
{
    binTree tree;
    const string spliter = "\n-----------------------------\n";

    /* Test Data */
    cout << "\n\n(1) Test string from teacher's blog: " << spliter;
    tree.construct("A B(A) C(A) D(BR) E(C) F(C) G(E) H(E)");
    tree.print();

    cout << "\n\n(2) A more complex tree: " << spliter;
    tree.construct("A U(A) H(A) B(U) G(U) X(B) Z(B) P(XR) L(H) W(H) D(L)");
    tree.print();

    cout << "\n\n(3) A tree like a linked list:" << spliter;
    tree.construct("A B(A) C(BR) D(C) E(D) F(ER) ");
    tree.print();

    cout << "\n\n(4) A tree with only a root:" << spliter;
    tree.construct("A ");
    tree.print();

    cout << "\n\n(5) Empty tree:" << endl;
    tree.construct("");
    tree.print();

    return 0;
}

